package com.example.demo.suanfa_sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * @program: java_base
 * @description: 归并排序
 * @author: zhouhongtao
 * @happyCreateTime: 2022/02/11 10:49
 */
public class MergeSortDemo {

    @Test
    public void mergeSort() {
        int[] arr = {34, 5, 2, 4, 6, 657, 678, 879, 0, 3, 22, 1};

        mergeSort(arr, 0, arr.length - 1);
        Arrays.stream(arr).forEach(System.out::println);

    }

    private void mergeSort(int[] arr, int l, int r) {
        if (l == r) {
            return;
        }
        int mid = l + ((r - l) >> 1);
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge_remember(arr, l, mid, r);
//        merge(arr, l, mid, r);
    }

    private void merge(int[] arr, int l, int mid, int r) {
        int[] dueRet = new int[r - l + 1];
        int j = 0;
        int p1 = l;
        int p2 = mid + 1;

        while (p1 <= mid && p2 <= r) {
            dueRet[j++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++];
        }

        while (p1 <= mid) {
            dueRet[j++] = arr[p1++];
        }

        while (p2 <= r) {
            dueRet[j++] = arr[p2++];
        }
        for (int i = 0; i < dueRet.length; i++) {
            arr[l + i] = dueRet[i];
        }
    }


    private void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }


    /**
     * 迭代版
     */
    @Test
    public void mergeSort2() {
        int[] arr = {43, 1, 2, 3, 54, 5};
        // 跳过固定的步长
        // i 为步长
        for (int i = 1; i < arr.length; i <<= 1) {
            // 比较 合并 步长内部的数据
            // j 为 第一组 左端点 索引
            for (int j = 0; j < arr.length; j += i) {
                // 左组最后一个位置
                int leftLastIndex = j + i - 1;
                if (leftLastIndex >= arr.length) {
                    break;// 说明 这一组超出了
                }
                // 右组 第一个位置 为 leftLastIndex += 1
                int rightFirstIndex = leftLastIndex + 1;
                // 最右能到达哪里
                int rightLastIndex = Math.min(i + rightFirstIndex, arr.length - 1);
                merge(arr, j, leftLastIndex, rightLastIndex);
                // 防止超过，整数最大值，超过后 变成负数了。越界了。
                if (i > arr.length >> 1) {
                    break;
                }
            }
        }
        Arrays.stream(arr).forEach(System.out::println);
    }

    /**
     * 回忆，理解 复习写
     * 犯错点：
     * 1.  i -= 1;  while (i >= 0) { } 此地需要先减去1 ，因为i++ 为下一个index
     * 2.   retArr[i++] = arr[s0] < arr[s1] ? arr[s0++] : arr[s1++];  符号写反了。
     *
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    public void merge_remember(int[] arr, int l, int mid, int r) {
        int[] retArr = new int[arr.length];
        int i = 0;
        int s0 = l;
        int s1 = mid + 1;
        while (s0 <= mid && s1 <= r) {
            retArr[i++] = arr[s0] < arr[s1] ? arr[s0++] : arr[s1++];
        }

        while (s0 <= mid) {
            retArr[i++] = arr[s0++];
        }
        while (s1 <= r) {
            retArr[i++] = arr[s1++];
        }

        // i为下一个索引位置 顾  i = index + 1 ，需要刨除==0位置
        i -= 1;
        while (i >= 0) {
            arr[r--] = retArr[i--];
        }
    }


    public void process01(int[] arr, int L, int R) {
        if (arr == null || arr.length == 0 || L >= R) {
            // throw new Exception()
            return;
        }
        int mid = L + ((R - L) >> 1);
        process01(arr, L, mid);
        process01(arr, mid + 1, R);
        merge01(arr, L, mid, R);
    }

    /**
     * @param arr
     * @param L
     * @param R
     */
    public void merge01(int[] arr, int L, int mid, int R) {
        if (arr == null || L >= R) {
            return;
        }
        int[] help = new int[R - L + 1];
        int p1 = L;
        int p2 = mid + 1;
        int i = 0;
        while (p1 <= mid && p2 <= R) {
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }

        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= R) {
            help[i++] = arr[p2++];
        }
        for (int j = 0; j < help.length - 1; j++) {
            arr[L + j] = help[j];
        }
    }
}
